#include <stdio.h>
#include <stdlib.h>

typedef struct no{
    int numero;
    struct no *proximo;
    struct no *anterior;
}No;

typedef struct lista{
    int totalNos;
    No *inicio;
    No *fim;
}Lista;

Lista *inicializaLista(){
	Lista *lista = (Lista*)malloc(sizeof(Lista));

	lista->totalNos = 0;
	lista->inicio = NULL;
	lista->fim = NULL;

	return lista;
}

void insereNumeroLista(Lista *lista, int numero){

	No *novo=(No*)malloc(sizeof(No));

	novo->numero = numero;
	novo->anterior = NULL;
	novo->proximo = NULL;

	if(lista->inicio == NULL){
		lista->totalNos++;
		lista->inicio= novo;
		lista->fim= novo;
	}
	else{
		lista->totalNos++;
		novo->anterior = lista->fim;
		lista->fim->proximo = novo;
		lista->fim = novo;
	}
}

void copylist(Lista *origem, Lista *destino){
    int i;
    No *o=origem->inicio;//nó para percorrer a lista
    No *d;//nó auxiliar para atribuir os indices

    for(i=0;i<origem->totalNos;i++){//percorre toda a lista
        insereNumeroLista(destino,o->numero);//insere na lista o valor contido na origem
        o=o->proximo;//avança para o proximo nó
    }

    d=destino->inicio;
    o=origem->inicio;

    for(i=0;i<origem->totalNos;i++){//percorre toda a lista
        //d->id=o->id;//atribui o indice da origem para o destino
        o=o->proximo;// avança para o proximo nó de origem
        d=d->proximo;//avança para o proximo nó de destino
    }
}

void divideLista(Lista *listaCompleta, Lista *listaEsquerda, Lista *listaDireita){//divide a lista em duas
    int i = 0, metadeNos = 0;

    No *Q = listaCompleta->inicio;//nó para percorrer a lista

    metadeNos = listaCompleta->totalNos / 2; //encontra o indice do meio
    for(i = 0; i < metadeNos; i++){//percorre a lista até o meio
        Q=Q->proximo;
    }
    //atribui os valores respectivos para a lista da esquerda
    listaEsquerda->inicio=listaCompleta->inicio;
    listaEsquerda->totalNos=metadeNos;
    listaEsquerda->fim = Q;

    //atribui os valores respectivos para a lista da direita
    listaDireita->inicio = Q->proximo;
    listaDireita->totalNos= listaCompleta->totalNos - metadeNos;
    listaDireita->fim = listaCompleta->fim;

}

struct no *merge2SortedLLs(struct no *head1, struct no *head2)
{
   struct no *a, *b, *c, *newHead/*, *temp*/;

   a = head1;
   b = head2;
   c       = (struct no *)NULL;
   newHead = (struct no*)NULL;


   if(a==NULL)return(b);
   else if(b==NULL)return(a);

   while(a!=NULL && b!=NULL)
   {
     if(a->numero < b->numero)
     {
       //printf("\na->value < b->value\n");
       if(c==NULL)
       {
         c  = a;
       }
       else
       {
         c->proximo = a;
         c = c->proximo;
       }
       a  = a->proximo;
     }
     else if(a->numero > b->numero)
     {
       //printf("\na->value > b->value\n");
       if(c==NULL)
       {
         c  = b;
       }
       else
       {
         c->proximo = b;
         c = c->proximo;
       }
       b  = b->proximo;
     }
     else
     {
       // Both are equal.
       // Arbitraritly chose to add one of them and make
       // sure you skip both!

       if(c == NULL)
       {
         c  = a;
       }
       else
       {
         c->proximo = a;
         c = c->proximo;
       }

       a  = a->proximo;
       b  = b->proximo;
     }

     // Make sure the new head is set...
     if(newHead == NULL)
      newHead = c;

   }

   if(a==NULL && b==NULL)
     return(newHead);

   if(a==NULL)
     c->proximo = b;
   else if(b==NULL)
     c->proximo = a;

   return(newHead);

}

void Merge(Lista *l,Lista *LEFT, Lista *RIGHT){
    No *left;//nó para comparações da lista da esquerda
    No *right;//nó para comparações da lista da direita
    No *list=l->inicio;//nó para percorrer a lista
    Lista *L=inicializaLista();//lista para ser copiada a lista da esquerda
    Lista *R=inicializaLista();//lista para ser copiada a lista da direita
    int i;

    copylist(LEFT,L);//copia o conteudo de LEFT para L
    copylist(RIGHT,R);//copia o conteudo de RIGHT para R

    left=L->inicio;
    right=R->inicio;

    insereNumeroLista(L,9999999);//insere valor "infinito"
    insereNumeroLista(R,9999999);

    for(i=0;i<l->totalNos;i++){//percorre toda a lista
        if(left->numero < right->numero){//compara se o valor da esquerda é maior que o valor da direita
            list->numero=left->numero;//copia pra lista o valor da esquerda
            left=left->proximo;//avança para o proximo nó da esquerda;
        }
        else{
            list->numero=right->numero;//copia o valor da direta para a lista
            right=right->proximo;//avança para o proximo nó da direita
        }
        list=list->proximo;//avança para o proximo nó da lista
    }

}

void mergeSort(Lista *lista){
    Lista *L=inicializaLista();//cria a lista da divisão da esquerda
    Lista *R=inicializaLista();//cria a lista da divisão da direita

    if (lista->totalNos > 1) {
		divideLista(lista,L,R);//divide a lista em duas
		mergeSort(L);//faz recursão para a lista da esquerda
		mergeSort(R);//faz recursão para a lista da direita
		Merge(lista,L,R);//funde as listas
	}
}




void criaListaEncadeada(Lista *lista, char nomeArquivo[]){
	int numeroArquivo = 0;
	FILE *fp;

	fp = fopen (nomeArquivo, "r");

	while(fscanf(fp,"%d", &numeroArquivo) != EOF){

		if (numeroArquivo != '\0' && numeroArquivo != EOF) {
			insereNumeroLista(lista, numeroArquivo);
		}
	}
	fclose (fp);
}

void salvaListaNoArquivo(Lista *lista, char nomeArquivo[]){
	FILE *fp;
	int resultado;
	No *noCorrente;

	fp = fopen (nomeArquivo, "w");
	if (fp == NULL) {
		printf ("Houve um erro ao abrir o arquivo.\n");
		return ;
	}


	noCorrente = lista->inicio;
	while( noCorrente != NULL ) {
		resultado = fprintf(fp,"%i ", noCorrente->numero);
		if (resultado == EOF){
			printf("Erro na Gravacao\n");
			return;
		}
		noCorrente = noCorrente->proximo;
	}

	fclose (fp);

}

void liberarLista(Lista *lista)
{
	if(lista->fim == NULL)
	{
		return;
	}
	No *noAtual = lista->inicio;
	while(noAtual != NULL)
	{
		No *temporario = noAtual;
		noAtual = noAtual->proximo;
		free(temporario);
	}
}

int main(int argc,char *argv[]){
	Lista *lista;

	lista = inicializaLista();

	criaListaEncadeada(lista, argv[1]);

	mergeSort(lista);

	salvaListaNoArquivo(lista, argv[2]);

	liberarLista(lista);

	return 0;
}
